/**
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * 实现词典类 WordDictionary ：
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 *示例：
 * 输入：
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * 输出：
 * [null,null,null,null,false,true,true,true]
 *
 * 解释：
 * WordDictionary wordDictionary = new WordDictionary();
 * wordDictionary.addWord("bad");
 * wordDictionary.addWord("dad");
 * wordDictionary.addWord("mad");
 * wordDictionary.search("pad"); // 返回 False
 * wordDictionary.search("bad"); // 返回 True
 * wordDictionary.search(".ad"); // 返回 True
 * wordDictionary.search("b.."); // 返回 True
 *
 *
 * 提示：
 *
 * 1 <= word.length <= 25
 * addWord 中的 word 由小写英文字母组成
 * search 中的 word 由 '.' 或小写英文字母组成
 * 最多调用 104 次 addWord 和 search
 * */
public class WordDictionary {
    static class Trie {
        private static class Node {
            Node[] children;
            boolean isEndOfWord;
            char val;

            Node(char c) {
                children = new Node[26];
                isEndOfWord = false;
                val = c;
            }

            Node() {
                this('\0');
            }
        }

        private Node root;

        public Trie() {
            root = new Node();
        }

        void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chars = word.toCharArray();
            Node curr = root;
            for (char c : chars) {
                Node[] childsNode = curr.children;
                if (childsNode[c - 'a'] == null) {
                    childsNode[c - 'a'] = new Node(c);
                }
                curr = childsNode[c - 'a'];
            }
            curr.isEndOfWord = true;
        }

        boolean search(String word, Node root, int index) {
            if (word == null) {
                return false;
            }
            if(index == word.length()) {
                return root.isEndOfWord;
            }
            if (word.charAt(index) == ANY_CHAR) {
                for (Node node: root.children) {
                    if (node != null && search(word, node, index + 1)) {
                        return true;
                    }
                }
                return false;
            }
            int idx = word.charAt(index) - 'a';
            if (root.children[idx] != null) {
                return search(word, root.children[idx], index + 1);
            }
            return false;
        }
    }
    static final char ANY_CHAR = '.';
    private Trie trie = new Trie();

    public WordDictionary() {

    }

    public void addWord(String word) {
        trie.insert(word);
    }

    public boolean search(String word) {
        return trie.search(word, trie.root, 0);
    }
}
